# 计算从三角顶到底最小路径（状态压缩）
'''
          2
        3   4
      6   5   7
    4   1   8   3
    答案是11
'''


def minimumTotal(triangel):
    if not triangel: return 0

    res = triangel[-1]
    for i in range(len(triangel) - 2, -1, -1):
        for j in range(len(triangel[i])):
            res[j] = min(res[j], res[j + 1]) + triangel[i][j]
    return res[0]


if __name__ == '__main__':
    a = minimumTotal([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]])
    print(a)
